1.什么是決策樹

決策樹是一種基本的分類和回歸方法，本文主要講解用于分類的決策樹。決策樹就是根據相關的條件進行分類的一種樹形結構，比如某高端約會網站針對女客戶約會對象見面的安排過程就是一個決策樹：

根據給定的數據集創建一個決策樹就是機器學習的課程，創建一個決策樹可能會花費較多的時間，但是使用一個決策樹卻非?？?。

創建決策樹時最關鍵的問題就是選取哪一個特征作為分類特征，好的分類特征能夠最大化的把數據集分開，將無序變為有序。這里就出現了一個問題，如何描述一個數據集有序的程度？在信息論和概率統計中，熵表示隨機變量不確定性的度量，即有序的程度。

現給出一個集合D，本文所有的討論都以該集合為例：

序號 不浮出水面是否可以生存 是否有腳蹼 是否為魚類
1?是?是?是?
2?是?是?是?
3?是?否?否?
4?否?是?否?
5?否?是?否

創建該集合的代碼如下：
def create_data_set():
dataSet = [[1,1,'yes'],
[1,1,'yes'],
[1,0,'no'],
[0,1,'no'],
[0,1,'no']]
labels = ['no surfacing', 'flippers'] #不浮出水面是否可以生存，是否有腳蹼
return dataSet, labels

2.熵，信息增益和信息增益比

2.1熵(entropy)

博主第一次接觸“熵”這個字，是在高中的化學課上，但是感覺“熵”在化學課上的含義和信息論中的含義沒什么區別，都是表示混亂的程度，熵越大，越混亂，比如一杯渾濁水的熵就比一杯純凈的水熵大。

在信息論和概率統計中，設X是一個取有限個值的離散隨機變量，其概率分布為：

編寫計算熵的函數，其中dataSet是建立決策樹的數據集，每行最后一個元素表示類別：
def cal_Ent(dataSet): #根據給定數據集計算熵
num = len(dataSet)
labels = {}
for row in dataSet: #統計所有標簽的個數
label = row[-1]
if label not in labels.keys():
labels[label] = 0
labels[label] += 1
Ent = 0.0
for key in labels: #計算熵
prob = float(labels[key]) / num
Ent -= prob * log(prob, 2)
return Ent

2.2信息增益(information gain)

信息增益表示得知特征X的信息而使得類Y的信息的不確定性減少的程度。

當熵和條件熵中的概率由數據估計得到時，所對應的熵與條件熵分別稱為經驗熵和經驗條件熵。

決策樹選擇某個特征作為其分類特征的依據就是該特征對于集合的信息增益最大，即去除該特征后，集合變得最有序。仍舊以給定的集合D為例，根據計算信息增益準則選擇最優分類特征。

以X1表示“不浮出水面是否可以生存”，則

編寫選擇最佳決策特征的函數，其中dataSet是建立決策樹的數據集，每行最后一個元素表示類別：
#按照給定特征劃分數據集，返回第axis個特征的值為value的所有數據
def split_data_set(dataSet, axis, value):
retDataSet = []
for row in dataSet:
if (row[axis]) == value:
reducedRow = row[:axis]
reducedRow.extend(row[axis+1:])
retDataSet.append(reducedRow)
return retDataSet

#選擇最佳決策特征
def choose_best_feature(dataSet):
num = len(dataSet[0]) - 1 #特征數
baseEnt = cal_Ent(dataSet)
bestInfoGain = 0.0
bestFeature = -1
for i in range(num):
featlist = [example[i] for example in dataSet] #按列遍歷數據集，選取一個特征的所有值
uniqueVals = set(featlist) #一個特征可以取的值
newEnt = 0.0
for value in uniqueVals:
subDataSet = split_data_set(dataSet, i, value)
prob = len(subDataSet) / float(len(dataSet))
newEnt += prob * cal_Ent(subDataSet)
infoGain = baseEnt - newEnt #信息增益
if (infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestFeature

ID3決策樹在生成的過程中，根據信息增益來選擇特征。

2.3信息增益比(information gain ratio)